

""" Giovanni's MicroCompiler Demo

<program>       ::=     { <id> ; <vars > <stmtlist>  }
<vars>          ::=     V { <id> ; }                       % declaration

<stmtlist>      ::=     <stmt> { ; <stmt> }
<stmt>          ::=     P <id>  |  <id> = <expr>      

<expr>          ::=     <factor> {  (+ | -)   <factor> }   % No precedence
<factor>                ::=     ID | Number                                                             

"""

import sys
import os.path

#===============================================================================
# # Lexical Analyser - the "Scanner" - Define the TokenTypes
#===============================================================================
tokenNames = \
  [ "programsym", "declaresym", "comma", "readsym", "dosym", "forever", "breaksym", "continuesym", # Chris add here 
    "unknownToken", "idsym", "assignsym", "leftbrace", "rightbrace", "doublequotes", "string", "nullstr",
    "varsym", "semicolon", "whilesym", "leftbracket", "rightbracket", "leftsbracket", "rightsbracket", "array",
    "printsym", "ifsym", "elsesym", "comment", "equals", "notequals", "lessthan", "greaterthan", "notsym", "notgreater", "notlesser",
    "number", "plus", "minus", "multiply", "divide", "function", "funid", "param", "returnsym", "endfile"]

# define the tokens as variables
# Chris add here 
programsym, declaresym, comma, readsym, dosym, forever, breaksym, continuesym, \
    unknownToken, idsym, assignsym, leftbrace, rightbrace, doublequotes, string, nullstr, \
    varsym, semicolon, whilesym, leftbracket, rightbracket, leftsbracket, rightsbracket, array, \
    printsym, ifsym, elsesym, comment, equals, notequals, lessthan, greaterthan, notsym, notgreater, notlesser, \
    number, plus, minus, multiply, divide, function, funid, param, returnsym, endfile = range(0, len(tokenNames))


#===============================================================================
class MemStack:
#===============================================================================
    # stack range from 500 to 1000
    minmemaddr = 500
    maxmemaddr = 1000
    stackpointer = minmemaddr
    
    def __init__(self):
        self.minmemaddr = 500
        self.maxmemaddr = 1000
        self.stackpointer = self.minmemaddr
    
    def __del__(self):
        pass
    
    def malloc(self):
        freeaddr = self.stackpointer
        
        if self.stackpointer < self.maxmemaddr:
            self.stackpointer += 1
        if self.stackpointer > self.maxmemaddr:
            self.stackpointer = self.minmemaddr
             
        return freeaddr
    
    def free(self):
        if self.stackpointer <= self.minmemaddr:
            self.stackpointer = self.minmemaddr


              
#===============================================================================
class symbol:
#===============================================================================
    name = None   # String representation
    token = None;  # Corresponding token
    address = 0;     # For variables, their runtime address
    value = None   # on defined for numbers

    def __init__(self, name, token, value=0):
        self.name = name
        self.token = token
        self.address = 0   # for identifiers, their address
        self.value = value   # for numbers, their value

              
symtbl = {}; # The Symbol Table, a dictionary of symbols indexed by name

#======================================================================
# GLOBALS for output of Lexical Analyser
# Set by each call to GeToken()

token = None;   # A symbol

isdeffunc = False

line = "\n" # the complex source file as a string
charIndex = 0    # the position in the source

linenumber = 0    # The current  number

EOF = chr(0)
#======================================================================
# Run Time Code Generation Variables

varptr = 1001   # Arbitrary base address of memory for variables
codeptr = 10    # Address to output next instruction (for code)

isdeclared = True
 
#===============================================================================
#                    Symbol Table Management Routines
#===============================================================================

#===============================================================================
def addToSymTbl (name, token):
#===============================================================================      
    global isdeffunc
    
    if isdeffunc:
        return addToFunTbl(name, token)
    else:
        symtbl[name] = symbol(name, token)  # Add a new symbol to the dictionary
        return symtbl[name]


#===============================================================================
def lookup (thisName): 
#===============================================================================
    "# Find a given identifier in the Symbol Table, Return the symtbl entry"
    global isdeffunc
    
    tmptoken = None
    expectoken = None
    
    if isdeffunc:
        tmptoken = lookuplocaltoken(thisName)
    
        if tmptoken is None:
            if symtbl.has_key(thisName):  # thisName has been seen before
                expectoken = symtbl[thisName]   # return the symtbl entry
            else: 
                expectoken = None
        else:
            expectoken = tmptoken
    else:
        if symtbl.has_key(thisName): # thisName has been seen before
             expectoken = symtbl[thisName] # return the symtbl entry
        else:
             expectoken = None

    return expectoken


#===============================================================================
def initSymTbl():
#===============================================================================
    "# Initialise Symbol Table, and preload reserved words"
    addToSymTbl('program', programsym)   # program
    addToSymTbl('function', function)   # function
    addToSymTbl('param', param)   # function parameter
    addToSymTbl('return', returnsym)
    addToSymTbl('declare', declaresym)   # declare
    addToSymTbl('var', varsym)   # VAR
    addToSymTbl('while', whilesym) # WHILE
    addToSymTbl('print', printsym) # PRINT
    addToSymTbl('if', ifsym)    # IF
    addToSymTbl('else', elsesym)    # else
    addToSymTbl('do', dosym)    # do
    addToSymTbl('forever', forever)    # do
    addToSymTbl('read', readsym)    # read
    addToSymTbl('break', breaksym)    # break
    addToSymTbl('continue', continuesym)    # continue
    addToSymTbl('string', string) # string
    addToSymTbl('nullstr', nullstr) # null string
    addToSymTbl('array', array) # array

    # Now add symbols - NB only single character symbols are here
    #                      multicharacter one like ">=" are still to do
    addToSymTbl('=', assignsym)
    addToSymTbl('#', comment) # comment
    addToSymTbl('!=', notequals)
    addToSymTbl('<', lessthan)
    addToSymTbl('>', greaterthan) 
    addToSymTbl('<=', notgreater) # not greater than
    addToSymTbl('==', equals) 
    addToSymTbl('>=', notlesser) # not greater than
    addToSymTbl('not', notsym) #notsym
    addToSymTbl('{', leftbrace)
    addToSymTbl('}', rightbrace)
    addToSymTbl('(', leftbracket)
    addToSymTbl(')', rightbracket)
    addToSymTbl('+', plus)
    addToSymTbl('-', minus)
    addToSymTbl('/', divide)
    addToSymTbl('*', multiply)
    addToSymTbl(';', semicolon)
    addToSymTbl(',', comma)     # comma
    addToSymTbl('"', doublequotes)     # double quotes
    addToSymTbl('[', leftsbracket)     #leftsbracket
    addToSymTbl(']', rightsbracket)    #rightsbracket
    addToSymTbl(EOF, endfile)


#===============================================================================
#                       Scanner Diagnostics
#===============================================================================
def printToken(tok):
#===============================================================================
    " - display the specified token."
    if tok.token == idsym or tok.token == string or tok.token == nullstr or tok.token == funid or tok.token == param:
        print "Token = %10s,  %-15s  adr = %3d" % \
             (tokenNames[tok.token], tok.name, tok.address)
    elif tok.token == number:
        print "Token = %10s  %d" % (tokenNames[tok.token], tok.value)
    else:
        print "Token = %10s" % tokenNames[tok.token]

#==============================?=================================================
def dumpSymTbl():
#===============================================================================
    """ Dump all the tokens in the symboltable """
    funlist = []
    print(" *** Symbol Table ***")
    for name in symtbl.keys():  # keys is a list of the names (printable form of tokens)
        tok = symtbl[name]
        if tok.token == idsym or tok.token == funid:
            printToken(tok)
            if tok.token == funid:
                funlist.append(tok) 
    
    for fun in funlist:
        paramlist = funtbl[fun.name]
        if len(paramlist) != 0:
            print("\n *** Local Symbol Table ***")
            for localtoken in paramlist:
                printToken(localtoken)
            print("\n\n")
#===============================================================================
def getch():
#===============================================================================
    global line
    global charIndex
    global linenumber
    
    global lastline
    global lastlinenumber
    global lastCharIndex
    
    while True:
        lastCharIndex = charIndex
        if charIndex < len(line):        # See if used up current line
            ch = line[charIndex]        # if not, get character
            charIndex = charIndex + 1     # & move pointer for next time
            
            if ch == "/" and charIndex < len(line) and line[charIndex] == "/":               # ignore the comments
                charIndex = len(line)
                continue
        else:
            line = srcfile.readline()
            if  line == "": 
                line = EOF
            charIndex = 0       # & reset character pointer
            linenumber = linenumber + 1
            continue
        
        if ch == "\n": 
            ch = " "                # A newline is a token separator
            lastline = line
            lastlinenumber = linenumber
        
            
        if ch == '?':
            dumpSymTbl()
            continue
        return ch   

#===============================================================================
def ungetch():
#===============================================================================
    """ Unget the next character peeked at when building variables, numbers
        and when distinguishing between >= and > ...
    """    
    global charIndex;
    charIndex = charIndex - 1;
    
#===============================================================================
def getoken():
#===============================================================================
    """ GETOKEN - Put next token into the global TOKEN """
    global token
    global isdeclared
        
    ch = getch()             # skip whitespace
    while ch in ["\t", " ", "\n"]: 
        ch = getch()    
    
    # If ch is alphabetic then this is start of reserved word or an identifier
    if ch.isalpha():  # Letter therefore it's either identifier or reserved word
        name = ""
        isPossibleArray = False
        while ch.isalpha() or ch.isdigit() or ch == "_" or ch == "[" or ch == "]" :
            if ch.isalpha():
                name = name + ch.lower()
            else:
                name = name + ch
            if ch == '[' or ch == ']':
                isPossibleArray = True
                
            ch = getch()

        ungetch()                             # let terminator be used next time
        
        isArray = False
        if isPossibleArray:
            isArray = isArrayToken(name) 
        
        token = lookup(name)                  # See if token's known
        if token is None:                     # if not
            if isdeclared == False:
                error("variable '"+name+"' is not declared!")
            if isArray:
                token = addToSymTbl(name, array)
            else:
                token = addToSymTbl(name, idsym)  #   add as 'idsym'-IDENTIFIER
        return   # we've set token.token to either id or tokentype of reserved word
          

    # If it's numeric return TOKEN=number & token.value = binary value
    elif ch.isdigit():
        # In the real version, build number and don't forget to end with ungetch()
        literalnum = ""
        while ch != "" and ch.isdigit():
            literalnum += ch
            ch = getch()
        ungetch()
                  
        token = symbol(literalnum, number, value=int(literalnum)) # simplistic SINGLE DIGIT Ascii to Binary
        return
    
    # Single character tokens
    elif ch in ["=", "#", "<", ">", "{", "}", "(", ")", "+" , "-" , ";",
                 ",", "*", "/", "\"", "[", "]", "!", EOF]:
        
        # ------------------ handle operators ------------------ #
        literaltoken= ch
        isString = False
        # get the token of <= | == | != | >=  
        if ch in ["<",">","!","="]:
            op = ch
            ch = getch()
            if ch == "=":
                op += ch 
            else:
                ungetch()
            literaltoken = op
            #token = lookup(op)
        
        # ------------------ handle string Begin ------------------ #
        if ch == "\"":
            isString = True
            strcontent = ""
            strlen = 0
            ch = getch()
            while ch != "\"":
                if ch == EOF:
                    error(" \" ( double quotes) expected at the end of string")
                strcontent = strcontent + ch
                strlen += 1
                ch = getch()
              
            if strlen == 0:  
                literaltoken = nullstr
              #token = lookup(nullstr)                  # See if token's known
            else:
                literaltoken = strcontent
              #token = lookup(strcontent)                  # See if token's known
          # ------------------ handle string END ------------------ #     
          
        token = lookup(literaltoken)  # preloaded with appropriate token  
        if token is None:
            if isString:                     # if not
                token = addToSymTbl(strcontent, string)  #   add as 'string'-IDENTIFIER
        return  # chris add here
        
    else:
        errMsg = "Unknown character -->%s<- decimal %d" % (ch, ord(ch))
        error(errMsg)
        sys.exit(1) # Abort Compilation

#======================================================================
def isArrayToken(arrayname):
#======================================================================    
    idxOfLeftBracket = arrayname.find('[')
    idxOfRightBracket = arrayname.find(']')
    
    if idxOfLeftBracket == -1 or idxOfRightBracket == -1:
        errMsg = "array name '" + arrayname + "' is invalid"
        error("errMsg")
        
    if idxOfLeftBracket >= idxOfRightBracket:
        errMsg = "array name '" + arrayname + "' is invalid"
        error("errMsg")
        
    arraylen = arrayname[idxOfLeftBracket + 1:idxOfRightBracket]
    if not arraylen.isdigit():
        errMsg = "the length of array '" + arrayname + "' must be digital"
        error("errMsg")
    elif int(arraylen) < 0:
        error("the length of an array must be greater than zero")
        
    return True

#======================================================================
def getLengthOfArray(arrayname):
#======================================================================
    
    idxOfLeftBracket = arrayname.find('[')
    idxOfRightBracket = arrayname.find(']')     
    
    arraylen = arrayname[idxOfLeftBracket + 1:idxOfRightBracket]
    if not arraylen.isdigit():
        return -1
    else:
        return int(arraylen) 

#======================================================================
def getNameOfArray(arrayname):
#======================================================================
    
    idxOfLeftBracket = arrayname.find('[') 
    
    return arrayname[0:idxOfLeftBracket]

#======================================================================
# THE GRAMMAR

# <program>       ::=     { <id> ; <vars > <stmtlist>  }
# <vars>          ::=     var { <id> ; }                    % declaration

# <stmtlist>      ::=     <stmt> { ; <stmt> }
# <stmt>          ::=     print <id>     
#                         <id> = <expr>  

# <expr>          ::=     <factor> {  (+ | -)   <factor> }   % No precedence
# <factor>        ::=     ID | Number                                                             

#======================================================================
#                  Centralised Parser Error Message handler
#======================================================================

#===============================================================================
def error (msg):
#===============================================================================
    global line
    global linenumber
    global charIndex
    global objpath
    global objfile
    
    global lastline
    global lastlinenumber
    global lastCharIndex
    
    exposi = lastCharIndex+1
    
    if charIndex != exposi-1:  # newline occurs
        errline = lastline
        errlinenum = lastlinenumber
        chposi = len(lastline)
    else:
        errline = line
        errlinenum = linenumber
        chposi = charIndex       
    
    tabnum = line.count("\t")
    if tabnum != 0:
        chposi += tabnum*7
        
      
    print("\n\n")
    print("============= compiler generates error report =============")
    print errline
    print "-" * (chposi-3), "^"
    print("Error on line: %d - index: %d\n" % (errlinenum + 1, chposi))
    print("Error type: \"%s\"\n" % msg)       
    if token is not None:
        printToken(token)
    print("\n")
    #raise Exception(msg)
    
    if objfile is not None:
        objfile.close()
    
    if os.path.exists(objpath):
        os.remove(objpath)
        
    sys.exit(1)

#===============================================================================
def emit (memadr, opcode, parameter):
#===============================================================================
    """EMIT CODE - Emit a  of code with a Parameter
    if first arg is zero - (the memory address), use and incr CODEPTR"""
    global codeptr
    
    if (memadr == 0):
        memadr = codeptr
        codeptr = codeptr + 1
    if opcode == "writech" or opcode == "readch" or opcode == "return":
        print "%6d  %-8s" % (memadr, opcode)
    else:
        print "%6d  %-8s %-7d" % (memadr, opcode, parameter)
    genCode(memadr, opcode, parameter)

#===============================================================================
def genCode (memadr, opcode, parameter):
    global objfile
    
    if opcode == "writech" or opcode == "readch" or opcode == "return":
        codeline = "%6d  %-8s\n" % (memadr, opcode)
    else:
        codeline = "%6d  %-8s %-7d\n" % (memadr, opcode, parameter)
    objfile.writelines(codeline)
    
    #print "%6d  %-8s %-7d" % (memadr, opcode, parameter)
#===============================================================================

#===============================================================================
def addToFunTbl (name, token):
#===============================================================================
    global funtoken
    
    vartoken = symbol(name, token)
    
    if funtbl.has_key(funtoken.name):
        localtoken = lookuplocaltoken(name)
        if localtoken is None:
            paramlist = funtbl[funtoken.name]
            paramlist.append(vartoken)
        else:
            return localtoken
    else:
        paramlist = [vartoken]
        funtbl[funtoken.name] = paramlist  # Add a new symbol to the dictionary
    
    return vartoken

#===============================================================================
def updateFunTbl (token):
#===============================================================================
    global funtoken
    global memstack
    
    tmptoken = lookuplocaltoken(token.name)
    
    paramlist = funtbl[funtoken.name]
    
    if tmptoken is None:
        vartoken = symbol(token.name, param)
        vartoken.address = memstack.malloc()
        
        
        paramlist.append(vartoken)
        funtbl[funtoken.name] = paramlist
        
    else:
        tmptoken.token = param
        tmptoken.address = memstack.malloc()
        for idx, ptoken in enumerate(paramlist):
            if ptoken.name == tmptoken.name:
                paramlist[idx] = tmptoken
                funtbl[funtoken.name] = paramlist
                break

#=============================================================================================
def lookuplocaltoken(tkname):
#=============================================================================================
    global funtoken    
    if funtoken is None:
        return None
    
    paramlist = funtbl[funtoken.name]
    
    if len(paramlist) == 0:
        return None
    
    tidx = 0
    for tk in paramlist:
        if tk.name == tkname:
            return paramlist[tidx]
        else:
            tidx += 1
            continue
    
    return None

#=============================================================================================
# variable-declaration        ::=    identifier    [  =  constant  |   "[" number "]"     ]  
def localvars() :
#=============================================================================================
    global memstack;
    global funtoken
    #global isdeffunc
    
    paramlist = funtbl[funtoken.name]
    
    if token.token == idsym:
        
        if token.address != 0:
            print("%c already declared\n", token.name);
        else:
            token.address = memstack.malloc();
            
    elif token.token == array:
        
            arrayname = getNameOfArray(token.name)
            arraylen = getLengthOfArray(token.name)
            
            i = 0
            while i < arraylen:
                name = arrayname + "[%d]" % i
                eletoken = addToFunTbl(name, idsym)
                eletoken.address = memstack.malloc()
                i += 1
  
    getoken()
    
#===============================================================================
def funcdeclaration() :
#===============================================================================    
    getoken()
    
    if token.token != idsym and token.token != array:
        error(" identifier only consist of 'A-Z { A-Z  _ 0-9 }'") 
    else:
        variable = token
        localvars()
        if token.token == assignsym:
            if variable.token == array:
                error("Array cannot be initialized!")
            elif variable.token == idsym:
                getoken()
                expression()
                emit(0, "store", variable.address)
        
        
    while (token.token == comma):
        
        getoken() #skip comma
        
        if token.token == idsym or token.token == array:
            variable = token
            localvars()
            if token.token == assignsym:
                if variable.token == array:
                    error("Array cannot be initialized!")
                elif variable.token == idsym:
                    getoken()
                    expression()
                    # Save result into LHS runtime address
                    emit(0, "store", variable.address)
                    
        elif token.token == endfile:
            error(" abnormal end of source file") 
           
        # if read a right bracket, terminate statement-list
        elif token.token == semicolon :
            error(" lack of variable declaration")
             
    if  token.token == semicolon:
        getoken()
        return
    
    elif token.token == endfile:
        error(" abnormal end of source file") 
    else:
        error("unexpected symbol '" + token.name + "', declaration must end with ';'") 
           

#===============================================================================
# VARIABLE declaration
#  declaration-list  ::=    variable-declaration { , variable-declaration }  ; 
#===============================================================================
def declaration() :
    global varptr;
    
    getoken()
    
    #dumpSymTbl()
    if token.token != idsym and token.token != array:
        error(" identifier only consist of 'A-Z { A-Z  _ 0-9 }'") 
    else:
        variable = token
        vars()
        if token.token == assignsym:
            if variable.token == array:
                error("Array cannot be initialized!")
            elif variable.token == idsym:
                getoken()
                expression()
                emit(0, "store", variable.address)
        
        
    while (token.token == comma):
        
        getoken() #skip comma
        
        if token.token == idsym or token.token == array:
            variable = token
            vars()
            if token.token == assignsym:
                if variable.token == array:
                    error("Array cannot be initialized!")
                elif variable.token == idsym:
                    getoken()
                    expression()
                    # Save result into LHS runtime address
                    emit(0, "store", variable.address)
                    
        elif token.token == endfile:
            error(" abnormal end of source file") 
           
        # if read a right bracket, terminate statement-list
        elif token.token == semicolon :
            error(" lack of variable declaration")
             
    if  token.token == semicolon:
        getoken()
        return
    
    elif token.token == endfile:
        error(" abnormal end of source file") 
    else:
        error("unexpected symbol '" + token.name + "', declaration must end with ';'") 
           
#=============================================================================================
# variable-declaration        ::=    identifier    [  =  constant  |   "[" number "]"     ]  
def vars() :
#=============================================================================================
    global varptr;
    
    if token.token == idsym:
        
        if token.address != 0:
            print("%c already declared\n", token.name);
        else:
            symtbl[token.name].address = varptr;
            varptr = varptr + 1
            
    elif token.token == array:
        
            arrayname = getNameOfArray(token.name)
            arraylen = getLengthOfArray(token.name)
            
            i = 0
            while i < arraylen:
                name = arrayname + "[%d]" % i
                eletoken = addToSymTbl(name, idsym)
                symtbl[eletoken.name].address = varptr
                varptr = varptr + 1
                i += 1
  
    getoken()

#=============================================================================================
# variable-declaration        ::=    identifier    [  =  constant  |   "[" number "]"     ]  
def arrays() :
#=============================================================================================
    global varptr;
    
    if token.address != 0:
        print("%c already declared\n", token.name);
    else:
        symtbl[token.name].address = varptr;
        varptr = varptr + 1
        
    getoken()        

#======================================================================
# STMTLIST 
# <stmtlist>  ::= <stmt> { ; <stmt> }

#===============================================================================
def stmtList():
#===============================================================================
    if token.token == leftbrace: 
        getoken() #bypass
    else: 
        error(" '{' expected at the begin of statement list")
        
    stmt()
    
       
    while (token.token == semicolon): #here is a bug
        getoken() #skip ;
        if token.token == rightbrace: 
            break
        else:
            stmt()
            
    if token.token != rightbrace:
        error(" '}' expected at the end of statement list")

#======================================================================
# STMT 

#===============================================================================
def stmt():
#===============================================================================
    """  <stmt> ::=   variable = expression               
                     | if  ( condition ) statement   [ else statement ]           
                     | while ( condition ) statement             
                     | statement-group           
                     | print   "("   print-item { , print-item }   ")"  
                     | read  "(" variable ")"            
                     | do statement-list forever        
                     | break                
                     | continue       
    """
    global isifmatched
    
    if  token.token == printsym:
        printStmt() 
        getoken() #move to next token

    elif token.token == idsym or token.token == array or token.token == param:
        assignStmt()   # () escapse from expression handle
        
    #elif token.token == ifsym or token.token == elsesym:
    elif token.token == ifsym:
        ifstmt()
        isifmatched = True
    
    elif token.token == elsesym:
        if isifmatched:
            elsestmt()
            isifmatched = False
        else:
            error(" no if-statement matched with this else-statement")
    
    elif token.token == whilesym:
        whilestmt()
        getoken() #move to next token
        
    elif token.token == dosym:
        dostmt()
        getoken() #move to next token
    
    elif token.token == readsym:
        readstmt()
        getoken() #move to next token
        
    elif token.token == breaksym:
        breakstmt()
        getoken() 

    elif token.token == continuesym:
        continuestmt()
        getoken() 
    
    elif token.token == funid:
        funtoken = token
        isdeffunc = True
        callfunc()
        funtoken = None
        isdeffunc = False
        #getoken() #skip function id
        
    elif token.token == returnsym:
        retnstmt()
                    
    if token.token != semicolon:
        error(" ';' semicolon expected at the end of statement")
#    elif token.token == leftbrace:
#        stmtList()
#    else: 
#        error("Expected start of a statement")
    
    #emit (0, "jumpDemo-to start of statement:  jump", thisStmtAdr)  # Jump DEMO

#===============================================================================
def whilestmt():
#===============================================================================
    """while ( condition ) statement | statement-group"""   
    global contidestaddr
    global breakdestaddr
    global codeptr
    
    if token.token == whilesym:
        getoken() #skip while
        
        if token.token == leftbracket:
            getoken()
        else:
            error(" '(' expected at the begin of the condition")
        
        whlstaddr = codeptr
        codeptr += 1
        emit(whlstaddr,"constant",codeptr)
        contidestaddr = whlstaddr
        
        whlendaddr = codeptr
        codeptr += 1
        breakdestaddr = whlendaddr
        
        condition(whlendaddr)
        
        if token.token == rightbracket:
            getoken()
        else:
            error(" ')' expected at the end of the condition")
        
        if token.token == leftbrace:
            
            stmtList()
                
            if token.token != rightbrace:
                error(" '}' expected at the end of while-statement")
        else:
            stmt()
            
        # jump to the start address of the while-condition 
        emit(0,"jumpi",whlstaddr)
        
        # the address for jumping to the end of while block
        emit(whlendaddr,"constant",codeptr)

#===============================================================================
def dostmt():
#===============================================================================
    """do statement-list forever """   
    global contidestaddr
    global breakdestaddr
    global codeptr
    
    if token.token == dosym:
        getoken() #skip do
    else:
        error(" '{' expected at the end of do-statement")
        
    if token.token != leftbrace:
        error(" '{' expected at the start of do-statement-list")
            
    dostaddr = codeptr
    codeptr += 1
    emit(dostaddr,"constant",codeptr)
    contidestaddr = dostaddr
    
    doendaddr = codeptr
    codeptr += 1
    breakdestaddr = doendaddr
    
    stmtList()
    # jump to the start address of the do statement 
    emit(0,"jumpi",dostaddr)
            
    if token.token != rightbrace:
        error(" '}' expected at the end of do-statement-list")
    
    getoken()
    
    if token.token != forever:
        error(" 'forever' expected at the end of do-statement ")
        
    emit(doendaddr,"constant",codeptr)
        
#===============================================================================
def breakstmt():
#===============================================================================  
    global breakdestaddr  
    
    if breakdestaddr != -1:
        # jump to the destination address 
        emit(0,"jumpi",breakdestaddr)


#===============================================================================
def continuestmt():
#=============================================================================== 
    global contidestaddr
    
    if contidestaddr != -1:
        # jump to the destination address 
        emit(0,"jumpi",contidestaddr)

#===============================================================================
def readstmt():
    
    if token.token == readsym:
        getoken()
    
    if token.token == leftbracket:
        getoken()
    else:
        error(" '(' expected at the begin of read")
    
    var = lookup(token.name)
    if var is None:
        error("variable '"+token.name+"' is not defined")
    
    emit(0, "ReadInt", var.address)
    
    getoken()
    
    if token.token != rightbracket:
        error(" ')' expected at the end of read")

#===============================================================================

#===============================================================================
def ifstmt():
#===============================================================================
    """ if  ( condition ) statement   [ else statement ] """
    global codeptr
    
    if token.token == ifsym:
        getoken() #skip if
        
        if token.token == leftbracket:
            getoken()
        else:
            error(" '(' expected at the begin of the condition")
        
        endifaddr = codeptr
        codeptr += 1
        
        condition(endifaddr)
        
        if token.token == rightbracket:
            getoken()
        else:
            error(" ')' expected at the end of the condition")
        
        if token.token == leftbrace:
            stmtList()
            #getoken()
            if token.token != rightbrace:
                error(" '}' expected at the end of if-statement")
            else:
                getoken() # move token to next which is semicolon
        else:
            stmt()
            
        # the address for jumping to the end of else block
        emit(endifaddr,"jumpi",codeptr)
        emit(endifaddr,"constant",codeptr)
    
#===============================================================================
def elsestmt():
#===============================================================================
    #TODO: else
    if token.token == elsesym:
        getoken() #skip else
        
        stmtoken = None
        
        if token.token == leftbrace:
            stmtList()
            if token.token != rightbrace:
                error(" '}' expected at the end of else-statement")
        else:
            stmt()
            
        #emit(endifaddr,"constant",codeptr)

#===============================================================================
def condition(destaddr):
#===============================================================================
    """ condition ::= [ not ]  conditional-expression  
    """
    tobenegated = False
    if token.token == notsym:
        tobenegated = True
        getoken()
    
    condexpr(destaddr)
    
#===============================================================================
def condexpr(destaddr):
#===============================================================================
    """
    conditional-expression    ::=    expression  [ relational-operator   expression ] 
    relational-operator       ::=    < | <= | == | != | > | >=
    """
    global codeptr
    global memstack
    
    expression()
    tmpaddr1 = memstack.malloc()
    emit(0,"store",tmpaddr1)
    
    conop = token
    if conop.name not in ["<","<=","==","!=",">",">="]:
        msg = "'" + conop.name +"' is not a conditional expression" 
        error(msg)
        
    getoken() # skip the conditional operator
    expression()
    tmpaddr2 = memstack.malloc()
    emit(0,"store", tmpaddr2)   # emit(0,"store", 1100)
    emit(0,"load", tmpaddr1)    # emit(0,"load", 1000)
    emit(0,"compare",tmpaddr2)   #emit(0,"load", 1100)

    if conop.token == lessthan:
        emit(0,"jumpeqi",destaddr)
        emit(0,"jumpgti",destaddr)
            
    elif conop.token == notgreater:
        emit(0,"jumpgti",destaddr)
        
    elif conop.token == equals:
        emit(0,"jumpnei",destaddr)
        
    elif conop.token == notequals:
        emit(0,"jumpeqi",destaddr)
        
    elif conop.token == greaterthan:
        emit(0,"jumpeqi",destaddr)
        emit(0,"jumplti",destaddr)
        
    elif conop.token == notlesser:
        emit(0,"jumplti",destaddr)

#===============================================================================
def printString():
#===============================================================================   
    global codeptr 
    if token.token == string :
        
        strcnst = token
        strcnst.address = codeptr
         
        for char in strcnst.name:
            emit(0,"constant",ord(char))
        endchaddr = codeptr
        emit(0,"constant",ord('0'))
        
        # using compiler-generated function, recursively invoke print character
        emit(0, "Loadv", strcnst.address) # load the first char address of string to index register
        emit(0, "store", 1)
        
        endaddr = codeptr
        codeptr += 1
        # print string 
        startaddr = codeptr
        emit(0, "Load-Ind", 0)           # 40     load-Ind     0 
        emit(0, "compare", endchaddr)
        emit(0, "jumpeqi", endaddr)    # 41     jumpeq       45 
        emit(0, "writech", 0)            # 42     writech
        emit(0, "increment", 1)          # 43     increment    1
        emit(0, "jump", startaddr)  # 44     jump       40
        emit(endaddr, "constant", codeptr)
#        emit(0,"loadv",ord('\n'))
#        emit(0,"WriteCh",0)
        
                                         
#===============================================================================
def printStmt():
#===============================================================================
    """ # print   "("   print-item { , print-item }   ")" 
        # print-item  ::=    expression | string """
    
    if  token.token == printsym:
        getoken() #skip print
    
    if token.token != leftbracket :
        error (" '(' expected ")
 
    getoken()    # skip "left bracket"
    
    
    if token.token == string :
        strcnst = token
        printString()
        getoken()
        emit(0,"loadv",ord(' '))
        emit(0,"writech",0)
         
    else :
        expression()          # on return, expr result (at runtime) will be in ACC
        emit(0, "WriteInt", 0)  # Memory address 0 is the ACC
        emit(0,"loadv",ord(' '))
        emit(0,"writech",0)
   
    
    while token.token == comma:
        getoken()
        if token.token == string :
            printString()
            getoken()
            emit(0,"loadv",ord(' '))
            emit(0,"writech",0)
        else :
            expression()          # on return, expr result (at runtime) will be in ACC
            emit(0, "WriteInt", 0)  # Memory address 0 is the ACC
            emit(0,"loadv",ord(' '))
            emit(0,"writech",0)
        
            
    emit(0, "loadv",ord('\n'))
    emit(0, "writech",0)
    
    if token.token != rightbracket :
        error (" ')' expected at the end of print-statement")
        
#===============================================================================
def assignStmt():
#===============================================================================
    """
        <id> = <expression> 
    """
    varid = token      # Remember which ID on Left
    getoken()                    # Get token after identifier
    if token.token == assignsym:
         getoken()
    else:
         error(" '=' expected within assignment statement")
    expression()
    # Save result into LHS runtime address
    emit(0, "store", varid.address)

#===============================================================================
# factor      ::=    [ + | - ] ( constant | variable | "(" expression ")" )  
# expression  ::=    term        {   (+ | - )   term   } 
# term        ::=    factor       {   ( * | / )  factor } 
# constant    ::=    a number 
def expression():
#===============================================================================
    """
       Leaves result in ACC at runtime 
       Use addresses 999 & 998 as Temporary variables
 
       <expression> ::=  <term> {  (+ | -)  <term> }
       <term> ::=  <factor> {  (* | /)  <factor> }
    """
    global memstack
    
    term()
    while token.token == plus or token.token == minus: 
        op = token                        # remember +/-
        getoken()                         # skip past +/-
        
        tmpaddr = memstack.malloc()
        
        emit(0, "store", tmpaddr)             # Save current result to temp memory location  emit(0, "store", 999) 
        term()                                # Evaluate next term, the result is saved in ACC
        if op.token == plus:
            emit(0, "add", tmpaddr)           # emit(0, "add", 999)
        elif op.token == minus:        # Subtract - have to swap operand order
            tmpaddr2 = memstack.malloc()
            emit(0, "store", tmpaddr2)         # emit(0, "store", 998)
            emit(0, "load" , tmpaddr)          # emit(0, "store", 9998)
            emit(0, "subtract", tmpaddr2)      # Leaves result in Acc  emit(0, "store", 998)

#===============================================================================
# factor      ::=    [ + | - ] ( constant | variable | "(" expression ")" )  
# expression  ::=    term        {   (+ | - )   term   } 
# term        ::=    factor       {   ( * | / )  factor } 
# constant    ::=    a number 
def term():
#===============================================================================
    """
      # term  ::=    factor  {   ( * | / )  factor } 
    """
    global memstack
    
    factor()
    while token.token == multiply or token.token == divide: 
        op = token                        # remember +/-
        getoken()                         # skip past +/-
                  
        tmpaddr = memstack.malloc()
        emit(0, "store", tmpaddr)             # Save current result emit(0, "store", 850)   
        factor()
        if op.token == multiply:
            emit(0, "MPY", tmpaddr)    # emit(0, "MPY", 850)
        elif op.token == divide:       # divide - have to swap operand order
            tmpaddr2 = memstack.malloc()
            emit(0, "store", tmpaddr2)         # emit(0, "store", 998)
            emit(0, "load" , tmpaddr)          # emit(0, "store", 9998)
            emit(0, "div", tmpaddr2)    # emit(0, "div", 850)

#===============================================================================
# factor      ::=    [ + | - ] ( constant | variable | "(" expression ")" )  
# expression  ::=    term        {   (+ | - )   term   } 
# term        ::=    factor       {   ( * | / )  factor } 
# constant    ::=    a number 
def factor():
#===============================================================================
    """
      # FACTOR() - leaves result in ACC at runtime
          <factor> ::=  [ + | - ] ( constant | variable | "(" expression ")" ) 
    """
    
    if token.token == idsym or token.token == param:
        emit(0, "load", token.address)
        getoken()
    
    elif token.token == array:
        emit(0, "load", token.value)
        getoken()
            
    elif token.token == number:
        emit(0, "loadv", token.value)
        getoken()
        
    elif token.token == minus:
        emit(0, "loadv", 0)
    
    elif token.token == funid:
        callfunc()
            
    elif token.token == leftbracket:
        getoken()
        expression()
        if token.token != rightbracket: 
            error("')' expected at the end of expression")
        else:
            getoken()
    else:
        error("Start of Factor expected")    # here is the problem  

#===============================================================================
def params():
#===============================================================================
    global funtbl
    global memstack
    global funtoken
    
    isdeffunc = True
        
    if token.token == leftbracket:
        getoken() # skip '('
        
    if token.token == rightbracket:  #no parameter need to be handled
        return
    
    if token.token == idsym:
        # change it to function param
        updateFunTbl(token)

    getoken()
    while token.token == comma:
        getoken() #skip comma
        if token.token == idsym:
            updateFunTbl(token)
            
            getoken() #skip comma
        else:
            error(" parameter expected")

#===============================================================================
def defunc():
#===============================================================================
    global codeptr
    global funtbl
    global funtoken
    global isdeffunc
    
    if token.token == function:
        getoken()
    
    # jump to the end of the function definition
    endaddr = codeptr
    codeptr += 1
    
    emit(0, "jumpi", endaddr)
    
    if token.token == idsym: 
        # change it to function name
        tmptoken = symbol(token.name, funid) 
        tmptoken.address = codeptr
        tmptoken.value = token.value
        del symtbl[token.name]
        symtbl[tmptoken.name] = tmptoken
        funtoken = tmptoken
        #update function table
        funtbl[tmptoken.name] = []  # Add a new symbol to the dictionary
        getoken()
    else: 
        error("function name expected")
    
    isdeffunc = True
    
    if token.token == leftbracket:
        getoken()
    else:
        error(" '(' expected at the start of function parameter declaration")    

    params()   

    if token.token != rightbracket:
        error(" ')' expected at the end of function parameter declaration")  
    else:
        getoken() # skip right bracket         
    
    if token.token == semicolon:
        getoken() # skip semicolon
        if token.token != declaresym:
            error(" declare expected after semicolon")
        else:
            funcdeclaration() #declaration()
        
    stmtList()
    emit(0, "return", 0)
    emit(endaddr, "constant", codeptr)
    funtoken = None
    isdeffunc = False
    #dumpSymTbl()
#===============================================================================
def callfunc():
#===============================================================================
    global funtbl
    global funtoken
    
    if token.token != funid:
        error("function name expected")
    # decr(num)
    else:
        funtoken = token #save function name
    getoken() #skip function id
    
    if token.token != leftbracket:
        error(" '(' expected at the start of calling function")
    getoken() #skip '('
    
    paramlist = funtbl[funtoken.name]
    
    pidx = 0
    param1 = paramlist[pidx]
    
    pnum = 0
    for p in paramlist:
        if p.token == param:
            pnum += 1
    
    
    if token.token == idsym:
        emit(0, "load", token.address)
        emit(0, "store", param1.address)
        getoken() #move to comman
        
    elif token.token == number:
        emit(0, "loadv", token.value)
        emit(0, "store", param1.address)
        getoken() #move to comman
        
    elif token.token == leftbracket:
        expression()
        emit(0, "store", param1.address)
        if token.token != rightbracket:
            error(" ')' expected at the end of expression")
    
    pidx += 1
    if pnum >= 1:
        pnum -= 1
    
    while token.token == comma:
        getoken() #skip comman
        param2 = paramlist[pidx]
        pidx += 1
        pnum -= 1
        
        if token.token == idsym:
            emit(0, "load", token.address)
            emit(0, "store", param2.address)
            getoken() #move to comman
        
        elif token.token == number:
            emit(0, "loadv", token.value)
            emit(0, "store", param2.address)
            
            getoken() #move to comman
        
        elif token.token == leftbracket:
            expression()
            emit(0, "store", param2.address)
            if token.token != rightbracket:
                error(" ')' expected at the end of expression")
    
    if pnum != 0:
        error("number of parameters is not currect!")
    
    if token.token != rightbracket:
        error(" ')' expected at the end of calling function")
    else:
        getoken() #skip ')'
        
    emit(0, "call", funtoken.address)
    funtoken = None
#===============================================================================
def retnstmt():
#===============================================================================
    if token.token != returnsym:
        error(" 'return' keyword expected")
    
    getoken() #skip return
    
    if token.token != leftbracket:
        error(" '(' expected at the start of return-statement")
    getoken() #skip '('
    
    # do expression
    expression()
        
    if token.token != rightbracket:
        error(" '(' expected at the start of return-statement")
    else:
        getoken() #skip ')'
        
    #emit(0, "return", 0) 
    
#===============================================================================
def program():
#===============================================================================
    """ # PROGRAM - Start production of the grammar
        #  <program> ::= { <id> ; <vars > <stmtlist>  }
    """
    global isdeclared
    global isifmatched
    global funtoken
    global isdeffunc
    
    isdeclared = True
    isdeffunc = False
    isifmatched = False
    funtoken = None
    
    if token.token == idsym: 
        getoken()
    else: 
        error("Program name expected")
        
    if token.token == semicolon: 
        getoken()
    else: 
        error("Semicolon expected")
    
    if token.token == declaresym:
        declaration()
        
    if token.token == function:
        defunc()
        getoken() 
        
    isdeclared = False
    
    stmtList()
    
    emit(0,"halt",0)
    
    if token.token == rightbrace: 
        print("\n*** Compilation finished ***\n")
    else: 
        error(" } expected")
    
    #dumpSymTbl()
# initialize compiler
#======================================================================
def initCompiler():
    global srcfile
    global objfile
    global vmexe
    global objpath
    
    global memstack
    global funtbl
    global funtoken
    
    funtoken = None
    vmexe= r"D:\CodeSpace\workspace\mycompiler\vm\VM.exe"
    
    funtbl = {}; # The function Table, a dictionary of symbols indexed by function name
                 # funame:paramlist
    
    # passed test case
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\fibfun.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\factorial.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\funexpr.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\funlocv.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\funparams.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\funnoparam.txt"
    srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\whltest.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\dobreak.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\doloop.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\elseblock.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\rationalexpr.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\ifblock.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\printest.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\aryinexpr.txt"
    #srcpath = r"D:\CodeSpace\workspace\MyCompiler\testcase\expr.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\simplevars.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\unaryminus.txt"
    #srcpath = r"D:\CodeSpace\workspace\mycompiler\testcase\arraytest.txt"
    
    # the path of object file which is generated by compiler 
    objpath = """D:\\CodeSpace\\workspace\\MyCompiler\\obj\\"""
    
    srcfile = open(srcpath, "r")
    
    extindex = srcpath.rfind(".");
    lastslash = srcpath.rfind("\\");
    objname = srcpath[lastslash + 1:extindex]
    objpath = objpath + objname + ".obj"
    
    if os.path.exists(objpath):
        os.remove(objpath)
        
    # Create a file object, in "write" mode
    objfile = open(objpath, "w")
    
    if not os.path.isfile(vmexe):
        print "virtual machine is not exist! compiler exit!"
        sys.exit(1)
    
    #init memory stack
    memstack = MemStack()
    
#======================================================================    
# Compiler main
#======================================================================
def main():
#======================================================================        
    global line
    global srcfile
    global charIndex
    global vmexe
    
    initCompiler()
           
    initSymTbl()
    
    line = srcfile.readline()        # readline
    

    charIndex = 0

    debugScanner = False
    if debugScanner:   # Scanner Test Routine - Read a line and display the tokens
       getoken()                       
       while token.token is not None:   # Skeleton for testing Scanner
           printToken(token)
           getoken()       
       sys.exit(1)
    else:                              
       getoken()                       # Parse Program according to the grammar
       if token.token == programsym: 
           getoken()
           program()                       # Call start non-terminal handler
       else: 
           error("program expected")

#======================================================================
def exeobj():
#======================================================================
    global objpath
    global vmexe
    
    if not os.path.isfile(vmexe):
        print "virtual machine is not exist! compiler exit!"
        sys.exit(1)
    
    if not os.path.isfile(objpath):
        print "object file '%s' is not exist!" %objpath
        sys.exit(1)
        
    cmd = "%s l ,%s"%(vmexe,objpath)
    print cmd
    os.system(cmd)
#===============================================================================
# Main Compiler starts here
#===============================================================================
print "Microcompiler.py v0.2"
main()
#   getoken()
        
#=======================================================================
# *** That's it folks - written by Giovanni Moretti - April 27, 2011 ***
#=======================================================================
